Auflistung nach Schlagwort "Computational complexity"

Auflistung nach Schlagwort "Computational complexity"

Sortiert nach: Sortierung: Ergebnisse:

  • Antenna subset selection for cyclic prefix assisted MIMO wireless communications over frequency selective channels 
    Wilzeck, A.; Kaiser, T. (Heidelberg : Springer Verlag, 2008)
    Antenna (subset) selection techniques are feasible to reduce the hardware complexity of multiple-input multiple-output (MIMO) systems, while keeping the benefits of higher-order MIMO systems. Many studies of antenna selection ...
  • Canonical models and the complexity of modal team logic 
    Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2018)
    We study modal team logic MTL, the team-semantical extension of classical modal logic closed under Boolean negation. Its fragments, such as modal dependence, independence, and inclusion logic, are well-understood. However, ...
  • The complexity of generalized satisfiability for linear temporal logic 
    Bauland, Michael; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert (Braunschweig : International Federation for Computational Logic, 2009)
    In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If, in contrast, the set ...
  • Connectivity of Boolean satisfiability 
    Schwerdtfeger, Konrad W. (Hannover : Gottfried Wilhelm Leibniz Universität Hannover, 2016)
    [no abstract]
  • Descriptive complexity of #AC0 functions 
    Durand, Arnaud; Haak, Anselm; Kontinen, Juha; Vollmer, Heribert (Saarbrücken : Dagstuhl Publishing, 2016)
    We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. ...
  • On the complexity of horn and krom fragments of second-order boolean logic 
    Hannula, Miika; Kontinen, Juha; Lück, Martin; Virtema, Jonni (Saarbrücken/Wadern, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2021)
    Second-order Boolean logic is a generalization of QBF, whose constant alternation fragments are known to be complete for the levels of the exponential time hierarchy. We consider two types of restriction of this logic: 1) ...
  • On the implicit graph conjecture 
    Chandoo, Maurice (Saarbrücken : Dagstuhl Publishing, 2016)
    The implicit graph conjecture states that every sufficiently small, hereditary graph class has a labeling scheme with a polynomial-time computable label decoder. We approach this conjecture by investigating classes of label ...
  • The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments 
    Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert (Amsterdam : Elsevier, 2009)
    In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If, in ...
  • Triangle density and contractibility 
    Kriesell, Matthias (Cambridge : Cambridge University Press, 2005)
    Let G be a noncomplete k -connected graph such that the graphs obtained from contracting any edge in G are not k-connected, and let t(G) denote the number of triangles in G. Thomassen proved t(G) ≥ 1, which was later ...
  • The weak base method for constraint satisfaction 
    Schnoor, Ilka (Hannover : Gottfried Wilhelm Leibniz Universität Hannover, 2008)
    [no abstract]